# 不太令人厌烦的堆排序
# “厌烦”的定义：一个元素被反复拉出来比较。
# ver 1.2:
#   修订引导, 增加出现的地方.
#   添加输入仅在一方的子串来支持此方.
#   添加是否进行非中文字符自动过滤的选项
#   添加完整经由路径的展示
#   改用大根堆，然后输出结果进行一个反序。
#   添加独立判断次数的统计，并和 n log2 n 做比较。
#   添加每次判断之前堆的备份，等以后做撤销判断

from functools import reduce
from re import sub


def throw(item):
    thrown.append(item)
    for z in items:
        judged[item, z] = 1  # newly thrown item is the smallest
        judged[z, item] = -1
    print("  你删除了", item)


def cmp(x, y):
    # return x >= y
    weaker = judged.get((x, y), 0)
    for z in via.get((x, y), []):
        if z in thrown:
            print("被 %s 背刺, 重新判断")
            weaker = 0  # 被已删元素背刺, 要重新直接判断
            via[(x, y)] = via[(y, x)] = []
    if weaker != 0:
        print("  调用: %s 比 %s %s更%s" % (x, y, side, "弱" if weaker != -1 else "强"))
    else:
        for z in items:
            if judged.get((x, z), 0) * judged.get((z, y), 0) == 1:
                weaker = judged[x, z]
                via[(x, y)] = via[(y, x)] = (
                    via.get((y, z), []) + [z] + via.get((x, y), [])
                    if weaker != -1
                    else via.get((x, z), []) + [z] + via.get((z, y), [])
                )
                print(
                    "  传递性: %s 比 %s %s更%s, 经由"
                    % (x, y, side, "弱" if weaker != -1 else "强"),
                    via[(x, y)],
                )
                break
    while weaker == 0:
        individual_judge.append(items.copy())
        # print('堆的现状:', items)
        ch = input("%s 和 %s %s? " % (x, y, side))
        if "" == ch or " " in ch:
            print(manual)
        elif ch in list("RD@Xx"):  # 扔掉右项
            throw(y)
            weaker = -1
        elif ch in tuple("LA!Xx"):  # 扔掉左项.
            throw(x)
            weaker = 1
        elif ch in set("la1"):  # 左项更强
            print("  %s %s更强" % (x, side))
            weaker = -1
        elif ch in "r d 2":  # 右项更强
            print("  %s %s更强" % (y, side))
            weaker = 1
        elif ch in x and ch not in y:  # 输入的东西只和左边相关, 代表认同左边
            print("  你认同 %s %s更强" % (x, side))
            weaker = -1
        elif ch in y and ch not in x:  # 输入的东西只和右边相关, 代表认同右边
            print("  你认同 %s %s更强" % (y, side))
            weaker = 1
        else:
            print("钝角")

    judged[x, y] = weaker
    judged[y, x] = -weaker  # 暂且不管 x=y 的情况
    return weaker != 1


# 向下调整. 采用非递归的实现
def heapify(arr, size, root):
    while 1:
        # 左子树 = root * 2 + 1,  右子树 = root * 2 + 2
        largest = reduce(
            lambda acmu, iter: acmu  # accumutive; iterative
            if iter >= size or cmp(arr[acmu], arr[iter])  # cmp(x, y) means x >= y
            else iter,
            [root, root * 2 + 1, root * 2 + 2],
        )
        if largest == root:
            return
        # 交换并考察子树
        arr[largest], arr[root], root = arr[root], arr[largest], largest


# main

judged = {}  # 已经判断过的
via = {}  # 经由三角形关系判断过的. 防止被已删元素背刺
thrown = []  # 删除记号, 链表, 保存的是各项的名字而不是序号
individual_judge = []  # 独立的判断, 即比强弱结果必须由人输入时的堆的副本

manual = """
输入小写的 l/r, a/d, 1/2 (并按回车) 来选择较强的一方. 
如果哪一项太烂了你无法评价, 那么输入大写的 L/R, A/D, !/@ 来扔掉它. 
两边都烂就输入 X/x 一起扔掉. 
这之外输入只属于一方的子串 (除了lradx12等的单字符) 也是选择该方. 
"""

# 输入, 以及修剪输入数据
srep = input("节奏榜生成器. 可以拖入文件或输入文件名, 或直接把单行文件内容贴在输入框. 按下回车继续(下同).\n")
try:
    with open(srep, "r", encoding="utf-8") as f:  # 打开文本
        srep = f.read()  # 读取文本
except OSError:
    print("输入数据已经读取.")
else:
    print("文件已经读取.")

# 不输入就是默认，默认就是去掉. 输入任何批话都是抬杠，抬杠就不去掉, 嗯留着。
ch = input("要不要去掉输入内容的数字/字母? (Y/N) ")
if (ch.isspace()) == (ch in "Yy"):  # 又不是没说，说的又不是“是”，那就是抬杠
    print("摆了")
else:
    srep = sub("WW| W ", " 达不溜 ", srep)  # 上保护基
    srep = sub("麒麟X夜刀", "麒麟爱克思夜刀", srep)
    srep = sub("火龙S黑角", "火龙爱思黑角", srep)
    srep = sub(r"[A-Za-z1-9Ѐ-ӿł'\.-]", " ", srep)
    srep = sub("爱思", "S", srep)
    srep = sub("爱克思", "X", srep)
    srep = sub("达不溜", "W", srep)  # 解保护基
    print("已经去掉了输入内容的大多数数字, 拉丁字母和西里尔字母, 但 W 和怪猎联动等特殊规则不变. ")


items = srep.split()
print(items)

side = input("比较哪个方面? 全方面比较就不填. ")
if side != "":
    side = "的" + side
print(manual)

# 堆排序
for i in range(len(items) // 2, 0, -1):
    heapify(items, len(items), i - 1)

for i in range(len(items) - 1, 0, -1):
    items[i], items[0] = items[0], items[i]  # swap
    heapify(items, i, 0)

# 堆中间的东西临时扔掉只做了删除记号, 还来不及和已经从小根堆顶拿出来的东西一拼高下
for z in thrown:
    items.remove(z)
items.reverse()

# 设置的梯队数目为总数的底 2 对数. 向上取整.
tiers = 0
scale = len(items)
while scale > 1:
    tiers += 1
    scale /= 2

# 如果总数达不到 2 的整数幂, 那么每个梯队的人往后匀一点.
even = lambda x: int(x * scale + 1 / 2)

print(
    "经过 %d 次独立判断, 得到节奏榜如下. 参考: n log2 n = %d"
    % (len(individual_judge), len(items) * tiers)
)

# 按杨辉三角第 tiers 行的组合数的值, 分配每个梯队的人数
total = 0
for i in range(tiers + 1):
    C_tiers_i = reduce(
        lambda acmu, iter: acmu * (tiers - iter) // (1 + iter), range(i), 1
    )
    print("Tier", i, ": ", items[even(total) : even(total + C_tiers_i)])
    total += C_tiers_i
if thrown != []:
    print(thrown, "没有人权. ")
# for i in individual_judge:
#     print(i)
input("请输入遗言 (按回车结束). ")
